Ana içeriğe geç

Hashing

Hashing, bir anahtar-değer ikilisine dayalı olarak verileri depolamak ve aramak için kullanılan bir yöntemdir. Bu yöntemde, anahtar değerleri özel bir matematiksel işleme tabi tutularak, bu işlem sonucunda elde edilen değere göre bir dizi indeksleri belirlenir. Bu dizideki her bir indeks, bir kova (bucket) olarak adlandırılır ve her bir kova, bir değer depolayabilir.

Örneğin, bir telefon defteri uygulaması düşünelim. Bu uygulama, her bir kişi için bir isim ve telefon numarası ikilisini depolamak istiyor. Hashing kullanarak, kişilerin isimleri özel bir matematiksel işleme tabi tutulur ve bu işlemin sonucunda elde edilen değere göre bir dizi indeksler belirlenir. Bu dizideki her bir indeks, bir kova (bucket) olarak adlandırılır ve her bir kova, bir kişinin isim-telefon numarası ikilisini depolayabilir.

Hashing'in avantajı, anahtar-değer ikililerini çok hızlı bir şekilde depolayabilmesi ve arayabilmesidir. Hashing kullanarak bir veri yapısı oluşturulduğunda, bir anahtara karşılık gelen değer hızlı bir şekilde bulunabilir. Ancak, hashing'in dezavantajı, çakışma (collision) adı verilen durumlarda ortaya çıkabilir. Çakışma, farklı anahtar değerlerinin aynı indekse (kova) atanması durumudur. Bu durumda, farklı anahtar-değer ikililerinin aynı kovada saklanması gerekebilir ve bu, veri yapısının performansını düşürebilir.

Separate Chaining (Collision Handling)​

Separate Chaining, hashing yöntemiyle verilerin depolanmasında kullanılan bir tekniktir. Bu teknikte, her bir kova (bucket) bir bağlı liste (linked list) olarak düşünülür. Aynı indekse (kova) atanmış olan anahtar-değer ikilileri, aynı bağlı listeye eklenir.

Örneğin, bir telefon defteri uygulaması düşünelim. Bu uygulama, her bir kişi için bir isim ve telefon numarası ikilisini depolamak istiyor. Separate Chaining kullanarak, kişilerin isimleri özel bir matematiksel işleme tabi tutulur ve bu işlemin sonucunda elde edilen değere göre bir dizi indeksler belirlenir. Bu dizideki her bir indeks, bir kova (bucket) olarak adlandırılır ve her bir kova, bir bağlı liste olarak düşünülür. Eğer farklı anahtar değerleri aynı indekse atanırsa, bu anahtar değerleri aynı bağlı liste içinde depolanır.

Separate Chaining'in avantajı, çakışmaların yönetimi konusunda çok etkili olmasıdır. Eğer bir çakışma oluşursa, anahtar değerleri aynı bağlı liste içinde depolanarak yönetilebilir. Bu sayede, veri yapısının performansı düşmez ve hızlı bir şekilde anahtar değerlerine erişilebilir. Ancak, Separate Chaining'in dezavantajı, bellek kullanımıdır. Eğer bir bağlı liste çok uzun olursa, bu bağlı listeyi depolamak için gereken bellek miktarı da artacaktır.

Open Addressing (Linear Probing ve Quadratic Probing)​

Quadratic Probing yönteminde, bir çakışma oluştuğunda aynı indekse atanmış olan anahtar-değer ikilisi, birinci boş kova bulunana kadar bir artan katsayı (1, 2, 3, vb.) kullanılarak hash tablosu içinde sırayla yerleştirilir.

Örneğin, yine bir telefon defteri uygulaması düşünelim. Quadratic Probing yöntemi kullanarak, kişilerin isimleri özel bir matematiksel işleme tabi tutulur ve bu işlemin sonucunda elde edilen değere göre bir dizi indeksler belirlenir. Eğer farklı anahtar değerleri aynı indekse atanırsa, bu anahtar değerleri birinci boş kova bulunana kadar, bir artan katsayı kullanılarak sırayla yerleştirilir.

Open Addressing yöntemleri, Separate Chaining'e göre daha az bellek kullanır ve arama işlemlerinde daha az harici bellek erişimi gerektirir. Ancak, daha fazla çarpışma oluşma olasılığı vardır ve bu da performansı olumsuz yönde etkileyebilir.

 Lineer Probing Insert İşlemi (C Kodu)​

Aşağıda, Linear Probing yöntemi kullanarak bir hash tablosuna yeni bir anahtar-değer çifti ekleyen C kodu örneği verilmiştir:

#define SIZE 10 // Hash tablosunun boyutu

int hash(int key) {
    return key % SIZE; // Basit bir hash fonksiyonu
}

void insert(int hash_table[], int key, int value) {
    int index = hash(key);
    int i = 0;
    while (hash_table[(index + i) % SIZE] != -1) { // Boş kova bulana kadar döngüyü sürdür
        i++;
        if (i == SIZE) { // Hash tablosu dolu
            printf("Hash table is full.\n");
            return;
        }
    }
    hash_table[(index + i) % SIZE] = value; // Boş kova bulundu, değeri yerleştir
}

Bu örnekte, SIZE adında bir define sabiti tanımlanmıştır. hash() fonksiyonu, basit bir mod alma işlemi ile bir anahtarın hash tablosu içindeki indeksini belirlemektedir.

insert() fonksiyonu, hash tablosuna yeni bir anahtar-değer çifti eklemek için kullanılır. İlk olarak, anahtarın hash değeri hesaplanır ve bu değer bir indeks olarak kullanılır. Daha sonra, hash tablosunda bu indekste boş bir kova bulana kadar döngü içinde gezinilir. Boş bir kova bulunduğunda, değer bu kovaya yerleştirilir. Eğer hash tablosu dolu ise, ekleme işlemi yapılamaz ve bir hata mesajı yazdırılır.

Lineer Probing Search İşlemi C Kodu​

Aşağıda, Linear Probing yöntemi kullanarak bir hash tablosunda bir anahtarı arayan C kodu örneği verilmiştir:

#define SIZE 10 // Hash tablosunun boyutu

int hash(int key) {
    return key % SIZE; // Basit bir hash fonksiyonu
}

int search(int hash_table[], int key) {
    int index = hash(key);
    int i = 0;
    while (hash_table[(index + i) % SIZE] != -1) { // Boş kova bulana kadar döngüyü sürdür
        if (hash_table[(index + i) % SIZE] == key) { // Anahtar bulundu
            return (index + i) % SIZE;
        }
        i++;
        if (i == SIZE) { // Hash tablosunun tamamı gezildi, anahtar yok
            return -1;
        }
    }
    return -1; // Anahtar yok
}

Bu örnekte de SIZE adında bir define sabiti tanımlanmıştır. hash() fonksiyonu, basit bir mod alma işlemi ile bir anahtarın hash tablosu içindeki indeksini belirlemektedir.

search() fonksiyonu, hash tablosunda bir anahtarı aramak için kullanılır. İlk olarak, anahtarın hash değeri hesaplanır ve bu değer bir indeks olarak kullanılır. Daha sonra, hash tablosunda bu indeksten başlayarak bir döngü ile gezinilir. Anahtar bulunana kadar, bir sonraki kovaya geçilir. Eğer anahtar bulunursa, bu kovanın indeksi döndürülür. Eğer hash tablosunun tamamı gezilirse ve anahtar bulunamazsa, -1 değeri döndürülür.

Quadratic Probing C Kodu​

Quadratic Probing, Open Addressing yöntemlerinden biridir ve Lineer Probing'in dezavantajlarını gidermek için kullanılır. Aşağıda Quadratic Probing yöntemi kullanarak bir hash tablosuna veri eklemek için C kodu örneği verilmiştir:

#define SIZE 10 // Hash tablosunun boyutu
#define EMPTY -1 // Boş kova değeri

int hash(int key) {
    return key % SIZE; // Basit bir hash fonksiyonu
}

void insert(int hash_table[], int key) {
    int index = hash(key);
    int i = 0;
    while (hash_table[(index + i*i) % SIZE] != EMPTY) { // Boş kova bulana kadar döngüyü sürdür
        i++;
        if (i == SIZE) { // Hash tablosunun tamamı gezildi, ekleme yapılamaz
            printf("Hash tablosu dolu!\n");
            return;
        }
    }
    hash_table[(index + i*i) % SIZE] = key; // Anahtar ekle
}

Bu örnekte de SIZE adında bir define sabiti tanımlanmıştır. hash() fonksiyonu, basit bir mod alma işlemi ile bir anahtarın hash tablosu içindeki indeksini belirlemektedir.

insert() fonksiyonu, hash tablosuna bir anahtar eklemek için kullanılır. İlk olarak, anahtarın hash değeri hesaplanır ve bu değer bir indeks olarak kullanılır. Daha sonra, hash tablosunda bu indeksten başlayarak bir döngü ile gezinilir. Eğer boş bir kova bulunursa, anahtar bu kovaya eklenir. Eğer boş kova bulunamazsa, bir sonraki kovaya geçmek yerine Quadratic Probing yöntemi kullanılarak boş bir kova aranır. i değişkeni, karelerinde artarak bir sonraki kovaya geçişi sağlar. Eğer hash tablosunun tamamı gezilirse ve boş bir kova bulunamazsa, "Hash tablosu dolu!" mesajı ekrana yazılır.